package com.shm.leetcode;

/**
 * 1128. 等价多米诺骨牌对的数量
 * 给你一个由一些多米诺骨牌组成的列表 dominoes。
 *
 * 如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌，我们就认为这两张牌是等价的。
 *
 * 形式上，dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 等价的前提是 a==c 且 b==d，或是 a==d 且 b==c。
 *
 * 在 0 <= i < j < dominoes.length 的前提下，找出满足 dominoes[i] 和 dominoes[j] 等价的骨牌对 (i, j) 的数量。
 *
 * 示例：
 *
 * 输入：dominoes = [[1,2],[2,1],[3,4],[5,6]]
 * 输出：1
 *
 * 提示：
 *
 * 1 <= dominoes.length <= 40000
 * 1 <= dominoes[i][j] <= 9
 *
 * @author SHM
 */
public class NumEquivDominoPairs {
    /**
     * 超出时间限制
     *
     * @param dominoes
     * @return
     */
    public int numEquivDominoPairs(int[][] dominoes) {
        int n = dominoes.length;
        int ans = 0;
        for(int i=0;i<n-1;i++){
            int a = dominoes[i][0],b=dominoes[i][1];
            for(int j=i+1;j<n;j++){
                int c=dominoes[j][0],d=dominoes[j][1];
                if((a==c&&b==d)||(a==d&&b==c)){
                    ans++;
                }
            }
        }
        return ans;
    }

    /**
     * 思路及解法
     *
     * 本题中我们需要统计所有等价的多米诺骨牌，其中多米诺骨牌使用二元对代表，「等价」的定义是，在允许翻转两个二元对的的情况下，使它们的元素一一对应相等。
     *
     * 于是我们不妨直接让每一个二元对都变为指定的格式，即第一维必须不大于第二维。这样两个二元对「等价」当且仅当两个二元对完全相同。
     *
     * 注意到二元对中的元素均不大于 99，因此我们可以将每一个二元对拼接成一个两位的正整数，即 (x, y) \to 10x + y(x,y)→10x+y。这样就无需使用哈希表统计元素数量，而直接使用长度为 100100 的数组即可。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n)O(n)，其中 nn 是多米诺骨牌的数量。我们至多只需要遍历一次该数组。
     *
     * 空间复杂度：O(1)O(1)，我们只需要常数的空间存储若干变量。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/number-of-equivalent-domino-pairs/solution/deng-jie-duo-mi-nuo-gu-pai-dui-de-shu-li-yjlz/
     * @param dominoes
     * @return
     */
    public int numEquivDominoPairs_2(int[][] dominoes) {
        int[] num = new int[100];
        int ans = 0;
        for (int[] dominoe : dominoes) {
            int val = dominoe[0]<dominoe[1]?dominoe[0]*10+dominoe[1]:dominoe[1]*10+dominoe[0];
            //非常困惑，方法二中count += freq[num];，
            // 为什么能够保证累加下来得到是正确的骨牌对数量？
            // 原来是这样的，基于方法一，N个元素中取2得到的就是骨牌对的数量，这个公式N*(N-1)/2，不就是等差数列的公式，
            // 那么，对于方法二而言，count就是进行了等差数列的累加，即1+2+3...+N，实际上，就是1+2+3...+N=N*(N-1)/2
            ans+=num[val];
            num[val]++;
        }
        return ans;
    }

}
